package shortestPath;

public class DijkstraLimonBinaryHeapInt {
    private static int[][] dist;
    private static int[] array;
    private static int size=0, and=65535, bitShift=16;
    
	public static long ShortestPathTo(int[][] matrix, boolean showAnswer) {
		long startTime = System.currentTimeMillis();
		
		int max = 1<<29, len = matrix.length, temp, x=0, y=0;
		dist = new int[len][len];
		array = new int[len<<3];
		
		for(int i=0; i<dist.length; i++)
			for(int j=0; j<dist[0].length; j++) dist[i][j] = max;
		dist[0][0] = matrix[0][0];
		add(0);
		
		while(size!=0){
			int next = array[1];
			array[1] = array[size--];

			bubbleDown();
			y=next>>bitShift;
			x=next&and;
			
			if(y>0 && (temp=dist[y][x] + matrix[y-1][x]) < dist[y-1][x]) {
				dist[y-1][x] = temp;
				add(((y-1)<<bitShift)+x);
			}
			if(y<len-1 && (temp=dist[y][x] + matrix[y+1][x]) < dist[y+1][x]) {
				dist[y+1][x] = temp;			
				add(((y+1)<<bitShift)+x);
			}
			if(x>0 && (temp=dist[y][x] + matrix[y][x-1]) < dist[y][x-1]) {
				dist[y][x-1] = temp;
				add((y<<bitShift)+x-1);
			}
			if(x<len-1 && (temp=dist[y][x] + matrix[y][x+1]) < dist[y][x+1]) {
				dist[y][x+1] = temp;
				add((y<<bitShift)+x+1);
			}
		}
		
		if(showAnswer) System.out.println(dist[len-1][len-1]);	
		return (System.currentTimeMillis()-startTime);
	}

	public static void add(int value) {
		array[++size] = value;
		bubbleUp();
	}

	protected static void bubbleDown() {
		int index = 1, smallerChild;

		while((smallerChild = index<<1) <= size) {
			if(smallerChild+1 <= size && compare(array[smallerChild], array[smallerChild+1]) > 0) smallerChild++;

			if(compare(array[index], array[smallerChild]) > 0) swap(index, smallerChild);
			else break;

			index = smallerChild;
		}        
	}

	protected static void bubbleUp() {
		int index = size;

		while(index>1 && (compare(array[index>>1], array[index]) > 0)) {
			swap(index, index>>1);
			index = index>>1;
		}        
	}

	protected static void swap(int index1, int index2) {
		int tmp = array[index1];
		array[index1] = array[index2];
		array[index2] = tmp;        
	}

    static int compare(int index1, int index2) {
    	return dist[index1>>bitShift][index1&and] - dist[index2>>bitShift][index2&and];
    }
}